Bootcamps
Masterclasses
Menu
Courses
Account
Login / Sign Up

Histogram Max Rectangular Area

Hard Acceptance 32.12% Points 40

You are given a histogram represented by an array arr, where each element represents the height of a bar, and all bars have a uniform width of 1 unit. Your task is to determine the largest rectangular area that can be formed using one or more consecutive bars in the histogram.

Examples
Example 1

Example 1

Input: arr[] = [6, 2, 5, 4, 5, 1, 6]

Output: 12

Explanation: The largest rectangle has a height of 4 and width of 3, giving an area of 4 × 3 = 12. This is formed by choosing the 3rd, 4th, and 5th bars.

Example 2

Example 2

Input: arr[] = [2, 4, 6, 3]

Output: 9

Explanation: The largest rectangle has a height of 3 and width of 3, giving an area of 3 × 3 = 9. This is formed by choosing the 2nd, 3rd, and 4th bars.

Constraints
  • 1 <= arr.size() <= 10^5
  • 0 <= arr[i] <= 10^3
Hints
  • Expected Time Complexity: O(n)
  • Expected Auxiliary Space: O(1)
Topics
Stack
Companies
Microsoft Google
Added 11 Apr 2025 32.12% acceptance
Ln 1, Col 1Sign in to save your code
6 2 5 4 5 1 6
12